package findTheDistanceValue;

import java.util.*;

public class Solution {
    public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
        // 1 8 9 10    2
        // 4 5 8
        // 二分查找
        Arrays.sort(arr2);
        int ans = 0;
        for (int x: arr1) {
            int l = 0,r = arr2.length-1; // 找x-d 或者 x+d
            boolean canAdd = true;
            while (l<=r) {
                int mid = (l+r)/2;
                if(arr2[mid] > x+d) {
                    r = mid-1;
                } else if (arr2[mid] <x-d) {
                    l = mid+1;
                } else {
                    canAdd = false;
                    break;
                }
            }
            if(canAdd) {
                ans++;
            }
        }
        return ans;
    }
    public String mergeAlternately(String word1, String word2) {
        int i = 0,j = 0;
        StringBuilder sb = new StringBuilder();
        while (i<word1.length() || j<word2.length()) {
            if(i == word1.length()) {
                sb.append(word2.charAt(j++));
            } else if (j == word2.length()) {
                sb.append(word1.charAt(i++));
            } else {
                sb.append(word1.charAt(i++));
                sb.append(word2.charAt(j++));
            }
        }
        return sb.toString();
    }
    public String reversePrefix(String word, char ch) {
        char[] chars = word.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            if(chars[i] == ch) {
                int l = 0,r = i;
                while (l<r) {
                    char c = chars[l];
                    chars[l++] = chars[r];
                    chars[r--] = c;
                }
                break;
            }
        }
        return new String(chars);
    }
    public String firstPalindrome(String[] words) {
        for (String s : words) {
            int l = 0,r = s.length()-1;
            boolean bol = true;
            while (l<r) {
                if(s.charAt(l++) != s.charAt(r--)) {
                    bol = false;
                    break;
                }
            }
            if(bol) return s;
        }
        return "";
    }
    public int arithmeticTriplets(int[] nums, int diff) {
        // 差值 == diff
        // 对于 nums[i] 找 nums[i]-diff nums[i]+diff
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            set.add(nums[i]);
        }
        int ans = 0;
        for (int i = 0; i < nums.length; i++) {
            if(set.contains(nums[i]-diff) && set.contains(nums[i]-2*diff)) {
                ans++;
            }
        }
        return ans;
    }
    public int findMaxK(int[] nums) {
        // 双指针
        Arrays.sort(nums);
        int i = 0,j = nums.length-1;
        while (nums[i] <0 && nums[j] > 0) {
            if(-nums[i] < nums[j]) {
                j--;
            } else if (-nums[i] > nums[j]) {
                i++;
            } else {
                return nums[j];
            }
        }
        return -1;
    }
    public int distinctAverages(int[] nums) {
        //
        Set<Double> set = new HashSet<>();
        Arrays.sort(nums);
        int i = 0,j = nums.length-1;
        while (i<j) {
            set.add((nums[i++]+nums[j--])*1.0/2);
        }
        return set.size();
    }
    public int getCommon(int[] nums1, int[] nums2) {
        //
        int i = 0,j = 0;
        while (i<nums1.length && j<nums2.length) {
            if(nums1[i] < nums2[j]) {
                i++;
            } else if (nums1[i] > nums2[j]) {
                j++;
            } else {
                return nums1[i];
            }
        }
        return -1;
    }
    public long findTheArrayConcVal(int[] nums) {
        long ans = 0;
        int i = 0,j = nums.length-1;
        while (i<=j) {
            if( i == j ) {
                ans+=nums[i];
                break;
            } else {
                ans += Long.parseLong(Integer.toString(nums[i])+Integer.toString(nums[j]));
                i++;
                j--;
            }
        }
        return ans;
    }
    public int countPairs(List<Integer> nums, int target) {
        Collections.sort(nums);
        int i = 0,j = nums.size()-1;
        int ans = 0;
        while (i < j) {
            if(nums.get(i) + nums.get(j) < target) {
                ans+= (j-i);
                i++;
            } else {
                j--;
            }
        }
        return ans;
    }
    public int breakfastNumber(int[] staple, int[] drinks, int x) {
        // 排序 + 双指针
        Arrays.sort(staple);
        Arrays.sort(drinks);
        int ans = 0,MOD = 1000000007;
        int i = 0,j = drinks.length-1;
        while (i<staple.length && j>=0) {
            if(staple[i] + drinks[j] <= x) {
                ans = (ans + j+1)%MOD;
                i++;
            } else {
                j--;
            }
        }
        return ans;
    }
    public int purchasePlans(int[] nums, int target) {
//        Arrays.sort(nums);
//        int i = 0,j = nums.length-1;
//        int ans = 0;
//        int mod = 1000000007;
//        while (i<j) {
//            if(nums[i] + nums[j] <= target) {
//                ans = (ans + j-i)%mod;
//                i++;
//            } else {
//                j--;
//            }
//        }
//        return ans;

        Arrays.sort(nums);
        int ans = 0,mod = 1000000007;
        for (int i = 0; i < nums.length; i++) {
            ans = (ans+binarySearch(nums,target-nums[i],i+1,nums.length-1))%mod;
        }
        return ans;
    }
    private int binarySearch(int[] nums,int target,int l,int r) {
        int start = l;
        while (l<=r) {
            int mid = (l+r)/2;
            if(nums[mid] <=target ){
                l = mid+1;
            } else {
                r = mid-1;
            }
        }
        return l == start?0:l-start;
    }
    public int[] twoSum(int[] numbers, int target) {
        // 找到目标等于 target
        int i = 0,j = numbers.length-1;
        while (i<j) {
            if(numbers[i] + numbers[j] < target) {
                i++;
            } else if (numbers[i] + numbers[j] > target) {
                j--;
            } else {
                return new int[]{i,j};
            }
        }
        return null;
    }

}
